package 中等.链表;

import util.ListNode;

import java.util.*;

/**
 * 给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。
 * 每个节点 被选中的概率一样 。
 * 实现 Solution 类：
 * Solution(ListNode head) 使用整数数组初始化对象。
 * int getRandom() 从链表中随机选择一个节点并返回该节点的值。
 * 链表中所有节点被选中的概率相等。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-random-node
 */
public class 链表随机节点_382 {

    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        Solution3 solution = new Solution3(listNode1);
        System.out.println(solution.getRandom());

    }

}

class Solution {

    private int count;

    private Map<Integer, Integer> map = new HashMap<>();

    public Solution(ListNode head) {
        while (head != null) {
            map.put(++count, head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        Random random = new Random();
        int ran = random.nextInt(count) + 1;
        return map.get(ran);
    }

}

/**
 * 用list存储就行，map需要额外的空间
 * random对象饿汉模式创建
 */
class Solution2 {

    private Random random = new Random();

    private List<Integer> list = new ArrayList<>();

    public Solution2(ListNode head) {
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
    }

    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }

}

/**
 * 水塘抽样算法
 * 结论：
 * 假如有n个样本，并且n是不确定的，从1开始遍历到n，遍历到k时，从[1,k]中随机取一个
 * 元素的概率为 1/k ，并且， >k&&<=n 之间的元素范围，[1,k+1]，[1,k+2]，...[1,n]
 * 均不能选中k时，那么选中k在整个样本中概率为 1/n
 * <p>
 * 思路：
 * 选中第1个元素的概率是1/n的条件是
 * 1/1*(加上后面元素的所有情况都不会选中第1个元素)=1/n
 * 选中第2个元素的概率是1/n的条件是
 * 1/2*(加上后面元素的所有情况都不会选中第2个元素)=1/n
 * 这个时候，没有选中第二个元素，那么仍然属于选中第1个元素时的条件
 */
class Solution3 {

    private Random random = new Random();

    private ListNode tempHead;

    public Solution3(ListNode head) {
        tempHead = head;
    }

    public int getRandom() {
        int k = 1;
        int ans = 0;
        for (ListNode curNode = tempHead; curNode != null; curNode = curNode.next) {
            if (random.nextInt(k) == 0) {  // 1/k的几率选中当前元素，因为[0,k)，k是递增的，==0每次都能取到1/k的概率
                ans = curNode.val;
            }
            k++;
        }
        return ans;
    }

}